Masala #0558

Lochinbek so'ngi kunlarda Z-funksiya mavzusida ko'p bilimlarga ega bo'ldi. U bilib olgan narsalari quyidagilar edi.

1. \(S\) satr deb \(S_1S_2S_3....S_{|s|}\) ko'rinishdagi satrga aytiladi. Bu yerda \(S_i\)  bu \(S\) satrning elementlari \(|S|\) esa \(S\) satrning uzunligi.
2. \(S[i..j] (1 ≤ i ≤ j ≤ |S|)\) qism satr deb \(S_iS_{i + 1}...S_j\) ko'rinishdagi satrga aytiladi.
3. \(S\) satrning \(L (1 ≤ L ≤ |S|)\)  uzunlikdagi prefiksi deb \(S[1..L]\) satrga aytiladi.
4. \(S\) satrning \(L (1 ≤ L ≤ |S|)\)  uzunlikdagi suffiksi deb \(S[|S|-L+1..|S|]\) satrga aytiladi.

Sizning vazifangiz \(S\) satrda ham prefiks, ham suffiks bo'la oladigan qism satrlar nechtaligini qaniqlash.

Bitta qatorda kichik lotin harflaridan tashkil topgan \(S_1S_2...S_{|s|} (1 ≤ |S| ≤ 10^5)\) satr.

Birinchi qatorda \(K\) soni. \(K\)-ham prefiks ham suffiks bo'la oladigan satrlar soni.
Keyingi \(K\) ta qatorda esa \(L_i C_i\) sonlari. \(Li\) ham prefiks ham suffiks bo'luvchi satr uzunligi \(C_i\) esa shu prefiks(suffiks) \(S\) satrda jami necha marotaba qism satr bo'lib kelganligi. \(L_i C_i\) juftliklari \(L_i\) o'sish tartibiga ko'ra chiqarilsin.